%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Cryptography
%% http://code.google.com/p/crypto-book/
%%
%% Copyright (C) 2007--2010 David R. Kohel <David.Kohel@univmed.fr>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Secret Sharing}
\label{SecretSharing}

A secret sharing scheme is a means for $n$ parties to carry
{\it shares} or {\it parts} $s_i$ of a message $s$, called
the {\it secret}, such that the complete set $s_1, \dots s_n$
of the parts determines the message.  The secret sharing scheme
is said to be {\it perfect} if no proper subset of shares leaks
any information regarding the secret.

{\bf Two party secret sharing.}
Let $s$ be a secret, encoding as an integer in $\Z/m\Z$.  Let
$s_1 \in \Z/m\Z$ be generated at random by a trusted party.
Then the two shares are defined to be $s_1$ and $s - s_1$.
The secret is recovered as $s = s_1 + s_2$.

{\bf Multiple party secret sharing.}
Let $s \in \Z/m\Z$ be a secret to be shared among $n$ parties.
Generate the first $n-1$ shares $s_1,\dots,s_{n-1}$ at random
and set
$$
s_n = s - \sum_{i=1}^{n-1}.
$$
The secret is recovered as $s = \sum_{i=1}^n s_i$.

A $(t,n)$ {\it threshold} secret sharing scheme is a method
for $n$ parties to carry shares $s_i$ of a message $s$ such
that any $t$ of the them to reconstruct the message, but so
that no $t-1$ of them can easy do so.  The threshold scheme
is {\it perfect} if knowledge of $t-1$ or fewer shares
provides no information regarding~$s$.

{\bf Shamir's $(t,n)$-threshold scheme}.
A scheme of Shamir provide an elegant construction of a perfect
$(t,n)$-threshold scheme using a classical algorithm called
Lagrange interpolation.  First we introduce Lagrange interpolation
as a theorem.

\begin{theorem}[Lagrange interpolation]
Given $t$ distinct points $(x_i,y_i)$ of the form $(x_i,f(x_i))$,
where $f(x)$ is a polynomial of degree less that $t$, then $f(x)$
is determined by
\begin{equation}
\label{lagrange}
f(x) = \sum_{i=1}^t y_i
    \prod_{\stackrel{\scr 1\le j \le t}{\scr i \ne j}}
        \frac{x-x_j}{x_i-x_j}.
\end{equation}
\end{theorem}

Shamir's scheme is defined for a secret $s \in \Z/p\Z$ with
$p$ prime, by setting $a_0 = s$, and choosing $a_1,\dots,a_{t-1}$
at random in $\Z/p\Z$.  The trusted party computes $f(i)$,
where
$$
f(x) = \sum_{k=0}^{t-1} a_k x^k,
$$
for all $1 \le i \le n$.  The shares $(i,f(i))$ are distributed
to the $n$ distinct parties.  Since the secret is the constant
term $s = a_0 = f(0)$, the secret is recovered from any $t$ shares
$(i,f(i))$, for $I \subset \{1,\dots,n\}$ by
$$
s = \sum_{i \in I} c_{i} f(i),
\hbox{ where each }
    c_{i} = \prod_{\stackrel{\scr j \in I}{\scr j \ne i}} \frac{i}{j-i}.
$$

{\bf Properties}. Shamir's secret sharing scheme is (1)
{\it perfect} --- no information is leaked by the shares,
(2) {\it ideal} --- every share is of the same size $p$ as the
secret, and (3) involves no unproven hypotheses.
In comparison, most public key cryptosystems rely on certain
well-known problems (integer factorization, discrete logarithm
problems) to be hard in order to guarantee security.

{\bf Proof of Lagrange interpolation theorem}.
Let $g(x)$ be the right hand side of~\eqref{lagrange}.  For
each $x_i$ in we verify directly that $f(x_i) = g(x_i)$, so
that $f(x)-g(x)$ is divisible by $x - x_i$.  It follows that
\begin{equation}
\label{zeropoly}
\prod_{i=1}^{t} (x-x_i) \big| (f(x)-g(x)),
\end{equation}
but since $\deg(f(x)-g(x)) \le t$, the only polynomial of this
degree satisfying equation~\eqref{zeropoly} is $f(x)-g(x) = 0$.


\noindent
{\bf Example.} Shamir secret sharing with $p = 31$.  Let the
threshold be $t = 3$, and the secret be $7 \in \Z/31\Z$. We choose
elements at random $a_1 = 19$ and $a_2 = 21$ in $\Z/31\Z$, and
set $f(x) = 7 + 19x + 21x^2$.  As the trusted party, we can now
generate as many shares as we like,
\begin{center}
\begin{tabular}{lll}
$(1,f(1)) = (1,16)$ & \quad & $(5,f(5)) = (5,7)$  \\
$(2,f(2)) = (2,5)$  & \quad & $(6,f(6)) = (6,9)$  \\
$(3,f(3)) = (3,5)$  & \quad & $(7,f(7)) = (7,22)$  \\
$(4,f(4)) = (4,16)$ & \quad & $(8,f(8)) = (8,15)$  \\
\end{tabular}
\end {center}
which are distributed to the holders of the share recipients, and
the original polynomial $f(x)$ is destroyed.  The secret can be
recovered from the formula
$$
f(x) = \sum_{i=1}^t y_i
   \prod_{\stackrel{1 \le i \le t}{i \ne j}} \frac{x - x_j}{x_i - x_j}
\quad =\rangle \quad
f(0) = \sum_{i=1}^t y_i
   \prod_{\stackrel{1 \le i \le t}{i \ne j}} \frac{x_j}{x_j - x_i}
$$
using any $t$ shares $(x_1,y_1),\dots,(x_t,y_t)$.  If we take the
first three shares $(1,16)$, $(2,5)$, $(3,5)$, we compute
$$
\begin{array}{ll}
f(0) & \dsp
     =  \frac{16 \cdot 2 \cdot 3}{(1-2)(1-3)}
      + \frac{5  \cdot 1 \cdot 3}{(2-1)(2-3)}
      + \frac{5  \cdot 1 \cdot 2}{(3-1)(3-2)} \\ \\
   & = 3 \cdot 2^{-1} + 15 \cdot (-1) + 10 \cdot 2^{-1}
     = 17 - 15 + 5 = 7.
\end{array}
$$
This agrees with the same calculation for the shares $(1,16)$, $(5,7)$,
and $(7,22)$,
$$
\begin{array}{ll}
f(0) & \dsp
     =  \frac{16 \cdot 5 \cdot 7}{(1-5)(1-7)}
      + \frac{7  \cdot 1 \cdot 7}{(5-1)(5-7)}
      + \frac{22 \cdot 1 \cdot 5}{(7-1)(7-5)} \\ \\
   & = 2 \cdot 24^{-1} + 18 \cdot (-8)^{-1} + 17 \cdot 12^{-1}
     = 13 + 21 + 4 = 7.
\end{array}
$$

\section*{Exercises}

%\begin{center}{\Large\bf MATH3024: Lecture 23}\end{center}

\ignore{
\chapter{Hash Functions}
\label{HashFunctions}

Cryptographic hash functions play a role in data integrity and
message authentication.  A hash function is a function from strings
of arbitrary finite bit length to strings of $n$ bits for some
fixed integer $n$.  A hash function is necessarily many-to-one, but
for cryptographic applications $n$ will be in the range of $128$
to $256$ bits and should satisfy much stronger conditions than
are required for typical hashing purposes.  These conditions are
classified by the difficulty of solving certain problems, as
presented in the table below.

\begin{tabular}{ll}
{\it Preimage resistance}: &
Given $H(x)$ find $y$ such that $H(y) = H(x)$. \\
{\it Second preimage resistance}: &
Given $x$, find $y$ such that $H(y) = H(x)$. \\
{\it Collision resistance}: &
Find $x$, $y$ such that $H(x) = H(y)$
\end{tabular}

Standard examples of hash functions are SHA-1 and MD5.

\begin{center}
{\large\bf Message Authentication Codes}
\end{center}

A message authentication code is a keyed hash function, such
that the hash value depends on an input key.  These have the
principle application to the problem of data integrity and message
authentication --- the hash value of a file or data plus the public
key of the originating party serve to verify that the data has not
been altered in transmission.

A message authentication code can be constructed from a block
cipher, such as DES, using CBC mode.  The protocol is given by
the following steps.

\noindent
{\bf Input:}
Message $m$, $n$-bit block cipher $E$, and secret MAC key $K$ for $E$.

\noindent
{\bf Algorithm:}

\noindent
1. Pad $m$ if necessary and subdivide it into $n$-bit blocks
$m_1, m_2,\dots m_t$.

\noindent
2. CBC processing: set $H_0 = 0\dots 0$, and compute
$H_i = E_K(m_i \oplus H_{i-1})$.

\noindent
{\bf Output:} $H_t$.
\vspace{0.2cm}

\noindent
{\bf N.B.} the message $m$ must be padding in a well-defined way.
Typically this involves adding a tail of all $0$'s to form a complete
block of length $n$.  This has the disadvantage that trailing $0$'s
of the message can not be distinguished from the padding.
Alternatively the message can be padded with a $1$ followed by all
$0$'s, which can be reversed by chopping off all final zeros and
the next $1$, but implies that a message block of which is already
a multiple of $n$-bits must adjoin an additional entire block of
$n$-bits.
}
